Graf (Graph) Örneği
Aşağıda, bir graf veri yapısını oluşturmak ve graf üzerinde işlemler yapmak için bir pseudo kod örneği verilmiştir:
// Graf veri yapısını oluşturma
graf = {}
// Düğüm ekleme işlemi
fonksiyon dugum_ekle(graf, dugum):
eger dugum zaten varsa geri don
graf[dugum] = []
// Kenar ekleme işlemi
fonksiyon kenar_ekle(graf, dugum1, dugum2):
eger dugum1 ya da dugum2 grafda yoksa geri don
graf[dugum1].ekle(dugum2)
graf[dugum2].ekle(dugum1)
// Grafı yazdırma işlemi
fonksiyon graf_yazdir(graf):
dongu dugum in graf:
yazdir(dugum, " -> ", graf[dugum])
// Test etmek için bir graf oluşturma
dugum_ekle(graf, "A")
dugum_ekle(graf, "B")
dugum_ekle(graf, "C")
dugum_ekle(graf, "D")
kenar_ekle(graf, "A", "B")
kenar_ekle(graf, "B", "C")
kenar_ekle(graf, "C", "D")
kenar_ekle(graf, "D", "A")
// Grafı yazdırma
graf_yazdir(graf)
Bu pseudo kod örneğinde, graf veri yapısının oluşturulması, düğüm ekleme işlemi, kenar ekleme işlemi ve grafın yazdırılması işlemleri yer almaktadır. İlk olarak, boş bir graf oluşturulur. Daha sonra, dugum_ekle() fonksiyonu ile düğümler eklenir. kenar_ekle() fonksiyonu ile iki düğüm arasına kenar eklenir ve graf oluşturulur. Son olarak, graf_yazdir() fonksiyonu ile oluşturulan graf ekrana yazdırılır.
Örnekte, oluşturulan graf A, B, C ve D düğümlerini ve bu düğümler arasındaki kenarları içermektedir. Ayrıca, grafı temsil etmek için iki fonksiyon kullanılmıştır.
Graf Tanımlama
Grafın pseudo kod ile tanımlanması aşağıdaki gibi olabilir:
GRAF Tanımla
düğümler = BOŞ
kenarlar = BOŞ
DÜĞÜM EKLE(d):
düğümler.EKLE(d)
KENAR EKLE(d1, d2):
kenarlar.EKLE(d1, d2)
kenarlar.EKLE(d2, d1)
Burada GRAF adlı bir veri yapısı tanımlanmıştır. düğümler adlı bir liste, graf içindeki düğümleri saklamak için kullanılırken, kenarlar adlı bir liste, düğümler arasındaki kenarları saklamak için kullanılır. DÜĞÜM EKLE adlı bir fonksiyon, yeni bir düğüm eklemek için kullanılırken, KENAR EKLE adlı bir fonksiyon, iki düğüm arasında yeni bir kenar eklemek için kullanılır.
Graf Kenarlarına ve Düğümlerine Erişim
Graf veri yapısındaki düğümlere ve kenarlara erişmek için aşağıdaki pseudo kodlar kullanılabilir:
GRAF DÜĞÜM_LİSTESİ():
DÖNDÜR düğümler
GRAF KENAR_LİSTESİ():
DÖNDÜR kenarlar
GRAF KENARLARI_GETİR(d):
kenar_listesi = BOŞ
DÖNGÜ kenar IN kenarlar:
EĞER kenar[0] == d:
kenar_listesi.EKLE(kenar[1])
DÖNGÜ SONU
DÖNDÜR kenar_listesi
GRAF DÜĞÜM_VAR_MI(d):
EĞER d IN düğümler:
DÖNDÜR DOĞRU
EĞER DEĞİLSE:
DÖNDÜR YANLIŞ
Burada, DÜĞÜM_LİSTESİ fonksiyonu, grafın içindeki tüm düğümleri bir liste olarak döndürür. KENAR_LİSTESİ fonksiyonu, grafın içindeki tüm kenarları bir liste olarak döndürür. KENARLARI_GETİR fonksiyonu, belirtilen düğüme bağlı olan kenarları bir liste olarak döndürür. DÜĞÜM_VAR_MI fonksiyonu, belirtilen düğümün graf içinde var olup olmadığını kontrol eder.
Grafın Komşuluk Matrisinin Hesaplanması
Grafın komşuluk matrisi, bir grafın düğümleri arasındaki bağlantıları gösteren bir matristir. Komşuluk matrisinin hesaplanması için şu pseudo kod kullanılabilir:
1. Grafın düğüm sayısını belirle
2. Boş bir matris oluştur ve boyutunu düğüm sayısı kadar ayarla
3. Grafın tüm kenarlarını döngü ile gez
4. Kenarın başlangıç düğümünün indeksini al
5. Kenarın bitiş düğümünün indeksini al
6. Matrisin ilgili konumunu 1 olarak ayarla
7. Döngüyü sonlandır
8. Matrisi döndür
Bu pseudo kod, grafın komşuluk matrisini hesaplamak için gerekli adımları gösterir. Döngü, grafın tüm kenarlarını gezerek, her bir kenarın başlangıç ve bitiş düğümlerinin indekslerini alır ve matrisin ilgili konumunu 1 olarak ayarlar. Matrisin boyutu, grafın düğüm sayısına eşittir ve tüm elemanları başlangıçta sıfır olarak ayarlanır.
Graf Yolunu Bulma
Graf üzerinde iki düğüm arasındaki yolun bulunması için genellikle genişlik öncelikli arama (breadth-first search) veya derinlik öncelikli arama (depth-first search) algoritmaları kullanılır. Bu algoritmaların pseudo kodları aşağıda verilmiştir:
Genişlik Öncelikli Arama (Breadth-First Search) Pseudo Kodu:
başlangıç düğümü s
hedef düğümü t
visited : ziyaret edilen düğümleri tutmak için set veri yapısı
queue : işlenecek düğümleri tutmak için kuyruk veri yapısı
enque(s) // başlangıç düğümünü kuyruğa ekle
visited.add(s) // başlangıç düğümünü ziyaret edildi olarak işaretle
while not queue.empty() do // kuyruk boşalana kadar
current = dequeue() // kuyruktan bir düğüm çıkar
if current = t then return "Yol bulundu!" // hedef düğüme ulaştık
for each neighbor of current do // düğümün komşuları için
if neighbor not in visited then // ziyaret edilmemişse
enque(neighbor) // kuyruğa ekle
visited.add(neighbor) // ziyaret edildi olarak işaretle
return "Yol bulunamadı." // hedef düğüme ulaşılamadı
- Aşağıda, derinlik öncelikli arama (DFS) algoritmasının bir pseudo kodu yer almaktadır:
DFS(G, u):
1. u ziyaret edilmiş olarak işaretle
2. u ile komşuları arasında yarım kalan kenarları kontrol et
3. varsa ziyaret edilmemiş komşularından biri v'yi seç ve DFS(G, v) çağrısı yap
4. adım 2'ye devam etmek için DFS(G, v) tamamlandıktan sonra
Burada, G grafı ve u başlangıç düğümüdür. DFS, bir düğümü ziyaret eder, ardından o düğümün komşularını ziyaret eder ve bu işlemi tekrarlar. Bu işlem, ziyaret edilmemiş tüm düğümleri ziyaret edene kadar devam eder. Bu algoritma, bir grafı ziyaret etmek veya bir düğümdeki bir hedef düğüme kadar yolları aramak için kullanılabilir.
Graf Kesitlerinin Bulunması
Graf kesitleri, bir grafiğin iki ayrı bölgesine ayıran ve bu bölgeleri birbirinden ayıran kenarlardır. Aşağıdaki pseudo kod, verilen bir grafın kesitlerini bulmak için kullanılabilir:
fonksiyon kesitleri_bul(graf):
ziyaret_edilen_dugumler = küme()
kesitler = liste()
for düğüm in graf.düğümler:
if düğüm not in ziyaret_edilen_dugumler:
kesit = bfs(düğüm)
ziyaret_edilen_dugumler = ziyaret_edilen_dugumler birleştir kesit
kesitler ekle kesit
return kesitler
fonksiyon bfs(baslangic_dugumu):
ziyaret_edilen_dugumler = küme()
kesit = küme()
kuyruk = yeni_kuyruk()
kuyruk.ekle(baslangic_dugumu)
while kuyruk.boş_değilse():
dugum = kuyruk.ilk()
kuyruk.çıkar()
if dugum not in ziyaret_edilen_dugumler:
ziyaret_edilen_dugumler.ekle(dugum)
kesit.ekle(dugum)
for komsu in dugum.komsular:
if komsu not in ziyaret_edilen_dugumler:
kuyruk.ekle(komsu)
return kesit
Bu pseudo kod, BFS (genişlik öncelikli arama) algoritmasını kullanarak graf kesitlerini bulur. İlk olarak, ziyaret edilen düğümlerin bir kümesi ve kesitlerin bir listesi oluşturulur. Daha sonra, her düğüm için BFS çağrılır ve her kesit ziyaret edilen düğümler kümesine eklenir. Son olarak, kesitlerin listesi döndürülür.
Graf Boyama
Graf boyama, bir grafa verilen renkleri atayarak, her iki komşu düğümün aynı renge sahip olmadığından emin olmaya çalışır. Pseudo kodu aşağıdaki gibi olabilir:
Algoritma GrafBoyama(graf):
# Renk ataması yapılırken kullanılacak renkler
renkler = ["kırmızı", "yeşil", "mavi", "sarı"]
# Her düğüm için başlangıçta renk atanmaz
renk_atama = {}
# Grafın tüm düğümleri üzerinde dolaşılır
for düğüm in graf.düğümler():
# Düğüme henüz renk atanmamışsa
if düğüm not in renk_atama:
# Düğümün komşularının renkleri kontrol edilir
komşu_renkleri = [renk_atama[k] for k in graf.komşular(düğüm) if k in renk_atama]
# Mevcut renklerden biri kullanılmamışsa, düğüme o renk atanır
for renk in renkler:
if renk not in komşu_renkleri:
renk_atama[düğüm] = renk
break
# Düğümlerin renkleri yazdırılır
for düğüm, renk in renk_atama.items():
yazdır(düğüm, " düğümü ", renk, " renkli.")
Bu kod, verilen grafı en az sayıda renkle boyamak için bir algoritma uygular. Algoritma, her düğümü bir renk atayarak başlar ve ardından her komşusunun rengini kontrol eder. Eğer bir düğümün komşuları arasında bir renk kullanılmamışsa, o düğüme o renk atanır. Bu işlem tüm düğümler için tekrarlanır ve sonunda her düğümün bir renk atandığı bir boyama elde edilir.